package com.cet.qz.unit01.chapter1_3;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

/**
 * @program: algorithm
 * @description: Josephus问题
 * @author: 陈恩涛
 * @create: 2021-04-22 10:58
 **/
public class Qz1_3_37 {
    public static void main(String[] args) {
        System.out.print("请输入人数： ");
        int n = StdIn.readInt();
        System.out.print("数到几干掉一个人： ");
        int m = StdIn.readInt();

        //初始化
        Queue<Integer> queue = new Queue<Integer>();
        for (int i = 0; i < n; i++) {
            queue.enqueue(i);
        }

        //开始
        while (!queue.isEmpty()) {
            for (int i = 0; i < m-1; i++)//每M个人中，去掉最后一名（即第M名），所以将前M-1个人放在队尾，删掉第M个人。
            {
                queue.enqueue(queue.dequeue());
            }
            StdOut.print(queue.dequeue() + " ");
        }
        StdOut.println();//最后一个输出的数就是Josephus在队中的位置
    }
}

/*
*ps 0 1 2 3 4 5 6
*   1 2 3 4 5 6 7 (4+2)%7=6
*   3 4 5 6 7 1  (2+2)%6=4
*   5 6 7 1 3   (0+2)%5=2
*   7 1 3 5    (2+2)%4=0
*   3 5 7     (0+2)%3=2
*   7 3      (0+2)%2=0
*   7               0
*
* f(n) = [f(n -1) + m] % n
* */
